Problem statement: zenit15kkj

Ješitná mačka

Počet bodov: 40, časový limit: 3000ms

Mačka Muca býva na okraji malebnej deninky menom Kocúrkovo. Dnes v noci prespávala u svojej najlepšej kamarátky na opačnom konci dediny. S prvými lúčmi vychádzajúceho slnka si natiahla labky a vydala sa na cestu domov. Predsa len, raňajky doma sú raňajky doma a mačací metabolizmus si pýta pravidelnú stravu.

Muca, ako správna mačka, už dobre pozná všetky ulice v Kocúrkove, vie kade vedú a ako sú dlhé.

No cesta krížom cez dedinu nie je jednoduchá. Na niektorých uliciach totiž číhajú svorky psov, ktoré veru nemajú mačky v láske. Hneď, ako nejakú zbadajú, tak po nej vyštartujú a …

Muca však má v rukáve svoje mačacie eso – deväť životov. Keď prejde cez ulicu, na ktorej sú psy, tak len príde o jeden zo svojich životov a dostane sa na druhú stranu.

Ako slnko stúpa vyššie a vyššie, Muce začína škvŕkať brucho čím ďalej, tým viac. Už je tak hladná, že jej nevadí prebehnúť cez ulicu plnú psov, ak jej to zrýchli cestu domov. A keďže s prázdnym žalúdkom sa myslí ťažko, poprosila vás o pomoc s hľadaním cesty domov.

Úloha

Kocúrkovo je tvorené \(n\) očíslovanými križovatkami, medzi ktorými vedú rôzne dlhé ulice. Dostanete zoznam bezpečných a nebezpečných ulíc. Muca prechodom cez nebezpečnú ulicu stratí jeden zo svojich deviatich životov.

Mucina kamarátka býva na križovatke číslo \(1\), Muca na križovatke číslo \(n\). Nájdite dĺžku najkratšej cesty medzi kamarátkou a domovom a počet životov, ktoré jej po prejdení zostanú. Ak sa najkratšími cestami vie dostať domov s rôznym počtom životov, nájdite ten najväčší. Muce musí po návrate domov zostať aspoň jeden život.

Vstup a výstup

Prvý riadok vstupu obsahuje čísla \(n, m, k\) (\(1 \leq n \leq 10~000\); \(0 \leq m, k \leq 35~000\)) udávajúce počet križovatiek, počet bezpečných ulíc a počet nebezpečných ulíc.

Nasledujúcich \(m\) riadkov obsahuje čísla \(x_i, y_i, t_i\) (\(1 \leq x_i,y_i \leq n\); \(1 \leq t_i \leq 1000\)), kde \(t_i\) je dĺžka bezpečnej ulice medzi \(x_i\)-tou a \(y_i\)-tou križovatkou.

Nasledujúcich \(k\) riadkov obsahuje čísla \(x_i, y_i, t_i\) (\(1 \leq x_i,y_i \leq n\); \(1 \leq t_i \leq 1000\)), kde \(t_i\) je dĺžka nebezpečnej ulice medzi \(x_i\)-tou a \(y_i\)-tou križovatkou.

Medzi dvoma križovatkami vedie najviac jedna ulica.

Vypíšte dve medzerou oddelené čísla – najmenšiu vzdialenosť, ktorú musí Muca prejsť a koľko najviac životov jej vie po takto dlhej trase zostať. Ak sa Muca nevie dostať domov, vypíšte \(-1\).

Táto úloha má pomerne veľké vstupy, preto môže byť celkom náročné získať za ňu plný počet bodov v pomalších jazykoch, menovite v Pythone.

Oproti papierovým zadaniam sa zmenil časový limit, zvýšil sa na 3 sekundy. Taktiež sa zmenili obmedzenia na vstupy, teraz sú menšie. Posledná vec, ktorá sa mení oproti papierovému zadaniu, je formát vstupu. Ten je rovnaký ako v ukážkach vstupu.

Na prvom riadku je číslo \(n\), na druhom číslo \(m\), potom nasleduje \(m\) riadkov s popismi bezpečných ulíc. Nasleduje riadok s číslom \(k\) a po ňom \(k\) riadkov s popismi nebezpečných ulíc.

Príklady

Input:

3
2
1 2 10
2 3 10
1
1 3 1

Output:

1 8

Všimnite si, že aj keď sa Muca vie dostať domov bez straty života, zvolí si miesto toho kratšiu cestu.

Input:

10
0
9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1

Output:

-1